The present invention relates to a method for improving efficiency in mutual exclusion. In particular, the present invention relates to a method for improving efficiency in mutual exclusion for arbitrating a race condition of operations respectively executed by multiple tasks.
A recent operating system (hereinafter, abbreviated as an OS) or middleware enables multiple threads to operate asynchronously and in parallel. In some cases, the multiple threads simultaneously access a shared resource in a computer such as a certain area in a memory or an input/output device, for example. In addition, a program may include an instruction string (a critical section) which is executed by a certain thread, and during execution of which another thread must not concurrently execute its instruction. In these cases, mutual exclusion is required for arbitrating a race condition of operations executed by the competing threads.
Heretofore, an atomic operation instruction such as compare_and_swap has been used for achieving efficient mutual exclusion. The atomic operation instruction is efficient since the instruction can be executed in a user mode, and does not require returning a process to an OS for the mutual exclusion. However, the atomic operation instruction requires a longer execution time than other instructions (for example, a computing instruction, a reading instruction from a memory, and the like). For this reason, even by using the atomic operation instruction, a problem of the execution time required for the mutual exclusion sometimes occurs.
In order to solve the problem, the techniques have been proposed for shortening a time required for the mutual exclusion in a way that the atomic operation instruction is made unnecessary by providing a memory area indicating a state of acquiring a lock for each thread (see reference to: E. W. Dijkstra, Solution of a Problem in Concurrent programming and Control, CACM, 8(9), p. 569, 1965; and T. Onodera, K. Kawachiya, and A. Koseki, Lock Reservation for Java Reconsidered. Proc. ECOOP '04, pp. 560-584, 2004). In a case where these techniques are applied to a computer employing a weakly-ordered memory model, a memory barrier instruction is needed instead of the atomic operation instruction. The memory barrier instruction is an instruction to enable a content written in a memory by a processor to be referred to by another processor. In accordance with the memory barrier instruction, it is possible to forcibly enable a content written by a processor to be referred to by another processor even when a time lag occurs between a time of writing and a time when the written content is enabled to be referred to.
However, the memory barrier instruction also requires a longer time for the execution than the other instructions. Accordingly, the time required for the mutual exclusion may also become a problem even by employing these techniques.